Sparse Fast Fourier Transform for Exactly and Generally K-Sparse Signals by Downsampling and Sparse Recovery

摘要

Fast Fourier Transform (FFT) is one of the most important tools in digitalsignal processing. FFT costs O(N \log N) for transforming a signal of length N.Recently, Sparse Fourier Transform (SFT) has emerged as a critical issueaddressing how to compute a compressed Fourier transform of a signal withcomplexity being related to the sparsity of its spectrum. In this paper, a newSFT algorithm is proposed for both exactly K-sparse signals (with K non-zerofrequencies) and generally K-sparse signals (with K significant frequencies),with the assumption that the distribution of the non-zero frequencies isuniform. The nuclear idea is to downsample the input signal at the beginning;then, subsequent processing operates under downsampled signals, where signallengths are proportional to O(K). Downsampling, however, possibly leads to"aliasing." By the shift property of DFT, we recast the aliasing problem ascomplex Bose-Chaudhuri-Hocquenghem (BCH) codes solved by syndrome decoding. Theproposed SFT algorithm for exactly K-sparse signals recovers 1-\tau frequencieswith computational complexity O(K \log K) and probability at least1-O(\frac{c}{\tau})^{\tau K} under K=O(N), where c is a user-controlledparameter. For generally K-sparse signals, due to the fact that BCH codes are sensitiveto noise, we combine a part of syndrome decoding with a compressivesensing-based solver for obtaining $K$ significant frequencies. Thecomputational complexity of our algorithm is \max \left( O(K \log K), O(N)\right), where the Big-O constant of O(N) is very small and only a simpleoperation involves O(N). Our simulations reveal that O(N) does not dominate thecomputational cost of sFFT-DT.